/**
 * 
 */
package leetCode;

/**
 * @author zhong
 *
 */
public class MinimumAddtoMakeParenthesesValid {
	public int minAddToMakeValid(String S) {
		int left = 0, right = 0;
		int cnt = 0;
		for (int i = 0; i < S.length(); i++) {
			char ch = S.charAt(i);
			if (ch == '(') {
				left++;
			} else {
				right++;
			}
			if (left == right) {
				left = right = 0;
			} else if (right > left) {
				cnt++;
				left = right = 0;
			}
		}
		cnt += Math.abs(left - right);
		return cnt;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
